package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC138 {


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * @return:
     */
    public Node copyRandomList(Node head) {
        if (null == head) {
            return null;
        }

        //clone original list
        Node p = head;
        while (null != p) {
            Node temp = p.next;
            p.next = new Node(p.val);
            p = p.next;
            p.next = temp;
            p = temp;
        }

        //clone random node
        p = head;
        while (null != p) {
            if (null != p.random) p.next.random = p.random.next;
            p = p.next.next;
        }

        //break clone node
        p = head;
        Node cloneHed = head.next, cloneP = head.next;
        while (null != cloneP.next) {
            //break original list
            p.next = p.next.next;
            p = p.next;

            //break clone list
            cloneP.next = cloneP.next.next;
            cloneP = cloneP.next;
        }

        p.next = null;
        return cloneHed;
    }


    public static void main(String[] args) {
        LC138 an = new LC138();
        String test = "abbbbacd";
    }
}
